package searchtree;

public class BinarySearchTree {
    static class TreeNode{
        public int key;
        public TreeNode left;
        public TreeNode right;
        TreeNode(int key){
            this.key=key;
        }
    }
    public TreeNode root;

    /**
     * 插入函数构建二叉搜索树
     * 1.插入的节点一定在叶子上
     * 2.当cur为空的时候，节点插入到p的左边还是右边？需要判断
     * 3.插入的过程当中，如果有相同的数字，就 不能插入
     * @param key
     */
    public boolean insert(int key){
        //第一个节点
        if(root==null){
            root=new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent=null;
        while (cur!=null){
            if(cur.key<key){
                parent=cur;
                cur=cur.right;
                
            } else if (cur.key>key) {
                parent=cur;
                cur=cur.left;
                
            }else {
                return false;

            }
        }
        TreeNode node=new TreeNode(key);
        //当代码走到这cur为空,但是cur的结点已与key比较过等号的情况，所以不用再做else
        if(parent.key<key) {
            parent.right = node;
        }else {
            parent.left= node;
        }
        return true;

    }

    /**
     * 查找key
     * @param key
     * @return
     */
    public TreeNode search(int key){
        TreeNode cur=root;
        while (cur!=null){
            if(cur.key<key){
                cur=cur.right;
            } else if (cur.key>key) {
                cur=cur.left;

            }else {
                return cur;
            }
        }
        return null;

    }
    public boolean remove(int key){
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if(cur.key<key){
                parent=cur;
                cur=cur.right;
            } else if (cur.key==key) {
                //这里删除
                removeNode(parent,cur);
                return true;
            }else {
                parent=cur;
                cur=cur.left;
            }

        }
        return false;

    }
    private void removeNode(TreeNode parent,TreeNode cur){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            } else if (cur==parent.left) {
                parent.left=cur.right;
                
            }else {
                parent.right=cur.right;
            }

        } else if (cur.right==null) {
            if(cur==root){
                root=cur.left;
            } else if (cur==parent.left) {
                parent.left=cur.left;
                
            }else {
                parent.right=cur.left;

            }

        }else {//找cur左边的最大值或者右边的最小值即找直到左边为空或者右边为空的，下面这个是找右边最小值的
            TreeNode targetParent=cur;
            TreeNode target=cur.right;
            while (target.left!=null){
                targetParent=target;
                target=target.left;
            }
            cur.key=target.key;
            if(target==targetParent.left){
                targetParent.left=target.right;

            }else {
                targetParent.right=target.right;

            }

        }

    }
    //中序遍历
    public void inorder(TreeNode root){
        if(root==null)
            return;
        inorder(root.left);
        System.out.print(root.key+" ");
        inorder(root.right);

    }
}
